package com.zhupf.binarySearch;

import java.util.List;

/**
 * @author zhupf
 * @date 2024年01月23日 9:42
 * @Description 4. 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class FindMedianSortedArrays {

    public static void main(String[] args) {
        int[] num1 = {1, 3, 4, 9};
        int[] num2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(findMedianSortedArrays(num1, num2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int totalLen = m + n;
        if (totalLen % 2 == 0) {
            return (getKthElement(nums1, nums2, totalLen / 2) + getKthElement(nums1, nums2, totalLen / 2 + 1)) / 2.0;
        } else {
            return getKthElement(nums1, nums2, totalLen / 2 + 1);
        }
    }

    public static int getKthElement(int[] num1, int[] num2, int k) {
        int idx1 = 0;
        int idx2 = 0;
        int len1 = num1.length;
        int len2 = num2.length;
        while (true) {
            if (idx1 == len1) {
                return num2[idx2 + k - 1];
            }
            if (idx2 == len2) {
                return num1[idx1 + k - 1];
            }
            if (k == 1) {
                return Math.min(num1[idx1], num2[idx2]);
            }
            int mid = k / 2;
            //  比较 num1[idx1+k-1] 和 num2[idx2+k-1]; 的大小
            int newIdx1 = Math.min(idx1 + mid, num1.length) - 1;
            int newIdx2 = Math.min(idx2 + mid, num2.length) - 1;
            if (num1[newIdx1] <= num2[newIdx2]) {
                k = k - (newIdx1 - idx1 + 1);
                idx1 = newIdx1 + 1;
            } else {
                k = k - (newIdx2 - idx2 + 1);
                idx2 = newIdx2 + 1;
            }
        }
    }
}
